// 1、无头单向非循环链表实现
 public class SingleLinkedList {
 /*
 节点内部类
  */
 static class ListNode {
  public int val;
  public ListNode next;

  public ListNode(int val) {
   this.val = val;
  }

 }
 public  ListNode head;//不初始化，默认是null

    public void display(){
        ListNode cur=this.head;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }
     //头插法
     public void addFirst(int data){
          ListNode node= new ListNode(data);
          node.next=this.head;
          head=node;
     }
     //尾插法
     public void addLast(int data){
        ListNode node=new ListNode(data);
        ListNode cur=this.head;
        if(cur==null){
            this.head=node;
        }
        while(cur.next!=null){
            cur=cur.next;
        }
        cur.next=node;
     }
     //任意位置插入,第一个数据节点为0号下标
     public void addIndex(int index,int data)
             throws IndexWrongException{
      if(index<0||index>size()){
          throw new IndexWrongException("插入位置错误");
      }
      ListNode node=new ListNode(data);
      if(index==0){
          addFirst(data);
      }else if (index==size()){
          addLast(data);
      }else{
          ListNode cur=FindIndex(index);
          node.next=cur.next;
          cur.next=node;
      }

     }
     protected ListNode FindIndex(int index){
        ListNode cur=this.head;
        while(index-1!=0){
            cur=cur.next;
            index--;
        }
        return cur;
     }
     //查找是否包含关键字key是否在单链表当中
     public boolean contains(int key){
        ListNode cur=this.head;
        while(cur!=null){
            if(cur.val==key){
                return true;
            }
            cur=cur.next;
        }
      return false;

     }
     //删除第一次出现关键字为key的节点
     public void remove(int key) {
         if(this.head == null) {
             return;
         }
         //删除头节点
         if(this.head.val == key) {
             this.head = this.head.next;
             return;
         }
         ListNode flag=FindKey(key);
         if(flag==null){
             System.out.println("没有你要删除的数字");
         }
         flag.next=flag.next.next;

     }
     protected ListNode FindKey(int key){
        ListNode cur=this.head;
        while (cur.next!=null){
            if(cur.next.val==key){
                return cur;
            }
            cur=cur.next;
        }
        return null;
     }
     //删除所有值为key的节点
     public void removeAllKey(int key) {
        if(this.head==null){
            return;
        }
        ListNode prev=this.head;
        ListNode cur=this.head.next;
        while(cur!=null) {
            if (cur.val == key) {
                prev.next = cur.next;
                cur = cur.next;
            } else {
                prev = cur;
                cur = cur.next;
            }
            if (this.head.val == key) {
                this.head = this.head.next;
            }
        }
     }
     //得到单链表的长度
     public int size(){
      int count=0;
      ListNode cur=this.head;
      while(cur!=null){
          count++;
          cur=cur.next;
      }
      return  count;
     }

     public void clear(){
       this.head=null;

     }
 }
